package allod.som.upgma

import allod.som.Lattice
import collection.mutable
import collection.mutable.ListBuffer

/**
 * Created by IntelliJ IDEA.
 * User: allod
 * Date: 21 лют 2010
 * Time: 18:11:02
 */

/**
 * Implementation of optimal O(n^2)-time UPGMA algorithm
 */
object UPGMA {
  private var clusters: mutable.Set[Cluster] = null
  private var distanceMatrix: mutable.Map[Cluster, mutable.Map[Cluster, Double]] = null
  private var path: ListBuffer[Cluster] = null

  def process(lattice: Lattice): Cluster = {
    clusters = createInitialClusters(lattice)
    distanceMatrix = createDistanceMatrix(lattice)
    path = new ListBuffer[Cluster]()
    while (clusters.size != 1) {
      doIteration()
    }
    val result = clusters.elements.next
    clusters = null
    distanceMatrix = null
    path = null
    result
  }

  private def doIteration() {
    extension()
    reduction()
  }

  private def extension() {
    while (true) {
      if (path.isEmpty) {
        path + randomCluster()
      } else {
        val lastCluster = path.last
        val beforeLastCluster = path(path.size - 2)
        val min = computeMinValue(lastCluster)
        if (path.size > 1 && min == distanceMatrix(beforeLastCluster)(lastCluster)) {
          return
        } else {
          path + getMinCluster(lastCluster, min)
        }
      }
    }
  }

  private def randomCluster(): Cluster = clusters.elements.next

  private def computeMinValue(cluster: Cluster): Double = {
    var minValue = Math.MAX_DOUBLE
    for (c <- clusters; if c != cluster) {
      if (distanceMatrix(cluster)(c) < minValue)
        minValue = distanceMatrix(cluster)(c)
    }
    minValue
  }

  private def getMinCluster(cluster: Cluster, min: Double): Cluster = {
    for (c <- clusters; if c != cluster) {
      if (min == distanceMatrix(cluster)(c)) return c
    }
    throw new NoSuchElementException()
  }

  private def reduction() {
    val beforeLastCluster = path(path.size - 2)
    val lastCluster = path.last
    path -= beforeLastCluster
    path -= lastCluster
    clusters -= beforeLastCluster
    clusters -= lastCluster
    val height = distanceMatrix(beforeLastCluster)(lastCluster)
    val joinedCluster = new CompositeCluster(beforeLastCluster, lastCluster, "C" + clusters.size, height)
    clusters += joinedCluster
    distanceMatrix -= beforeLastCluster
    distanceMatrix -= lastCluster
    distanceMatrix += joinedCluster -> mutable.Map.empty[Cluster, Double]
    for (c <- clusters; if c != joinedCluster) {
      val c1 = beforeLastCluster.weight.asInstanceOf[Double] / (beforeLastCluster.weight + lastCluster.weight)
      val c2 = lastCluster.weight.asInstanceOf[Double] / (beforeLastCluster.weight + lastCluster.weight)
      val value = c1 * distanceMatrix(c)(beforeLastCluster) + c2 * distanceMatrix(c)(lastCluster)
      distanceMatrix(c) += joinedCluster -> value
      distanceMatrix(joinedCluster) += c -> value
      distanceMatrix(c) -= beforeLastCluster
      distanceMatrix(c) -= lastCluster
    }
  }

  private def createDistanceMatrix(lattice: Lattice): mutable.Map[Cluster, mutable.Map[Cluster, Double]] = {
    val matrix = mutable.Map.empty[Cluster, mutable.Map[Cluster, Double]]
    for (i <- clusters) {
      matrix += i -> mutable.Map.empty[Cluster, Double]
      val iNeuron = i.asInstanceOf[IdentityCluster].neuron
      for (j <- clusters; if i != j) {
        val jNeuron = j.asInstanceOf[IdentityCluster].neuron
        matrix(i) += j -> lattice.distanceToNeuron(iNeuron, jNeuron)
      }
    }
    matrix
  }

  private def createInitialClusters(lattice: Lattice): mutable.Set[Cluster] = {
    val clustersSet = mutable.Set.empty[Cluster]
    for{
      i <- 0 until lattice.columns
      j <- 0 until lattice.rows
    } clustersSet + new IdentityCluster((i, j))
    clustersSet
  }
}